#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

// Define Etype for the Binary Tree
typedef char Etype;

// Binary Tree Node Definition
typedef struct BiTNode {
    Etype data;
    struct BiTNode* lch;
    struct BiTNode* rch;
} BiTNode, * BiTree;

// Huffman Tree Node Definition
typedef struct hfmTNode {
    char data;
    int weight;
    struct hfmTNode* lChild;
    struct hfmTNode* rChild;
} HFMNode;

typedef struct {
    HFMNode** data;
    int size;
    int capacity;
} PriorityQueue;

BiTree CreateBinaryTree();  // Add the implementation for this function
HFMNode* HuffmanTreeFromBinaryTree(BiTree root);
HFMNode* CreateHuffmanNode(char data, int weight);
void BuildHuffmanCodes(HFMNode* root, char* code, char** huffmanCodes);
char** HuffmanEncode(HFMNode* root);
void HuffmanDecodeHelper(HFMNode* root, const char* encodedMessage);
void HuffmanDecode(HFMNode* root, const char* encodedMessage);

// Other Function Prototypes
BiTNode* creat_bt1();
BiTNode* creat_bt2();
void preorder(BiTNode* p);
void inorder(BiTNode* p);
void postorder(BiTNode* p);
void enqueue(BiTree);
BiTree delqueue();
void levorder(BiTree);
int treedepth(BiTree);
void prtbtree(BiTree, int);
void exchange(BiTree);
int leafcount(BiTree);
void paintleaf(BiTree);

#define M 100
BiTree que[M];
int front = 0, rear = 0;

BiTree creat_bt1() {
    // Create binary tree using method 1
    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->data = 'A';
    root->lch = (BiTree)malloc(sizeof(BiTNode));
    root->lch->data = 'B';
    root->lch->lch = NULL;
    root->lch->rch = NULL;
    root->rch = (BiTree)malloc(sizeof(BiTNode));
    root->rch->data = 'C';
    root->rch->lch = NULL;
    root->rch->rch = NULL;
    return root;
}

BiTree creat_bt2() {
    // Create binary tree using method 2, user inputs node values
    char data;
    scanf(" %c", &data);
    if (data == '#') {
        return NULL;
    }
    BiTree node = (BiTree)malloc(sizeof(BiTNode));
    node->data = data;
    node->lch = creat_bt2();
    node->rch = creat_bt2();
    return node;
}

void preorder(BiTNode* p) {
    // Preorder recursive traversal of the binary tree
    if (p) {
        printf("%c ", p->data);
        preorder(p->lch);
        preorder(p->rch);
    }
}

void inorder(BiTNode* p) {
    // Inorder recursive traversal of the binary tree
    if (p) {
        inorder(p->lch);
        printf("%c ", p->data);
        inorder(p->rch);
    }
}

void postorder(BiTNode* p) {
    // Postorder recursive traversal of the binary tree
    if (p) {
        postorder(p->lch);
        postorder(p->rch);
        printf("%c ", p->data);
    }
}

void enqueue(BiTree node) {
    que[rear] = node;
    rear = (rear + 1) % M;
}

BiTree delqueue() {
    BiTree temp = que[front];
    front = (front + 1) % M;
    return temp;
}

void levorder(BiTree root) {
    // Level order traversal of the binary tree
    if (!root) {
        return;
    }
    BiTree p = root;
    enqueue(p);
    while (front != rear) {
        p = delqueue();
        printf("%c ", p->data);
        if (p->lch) {
            enqueue(p->lch);
        }
        if (p->rch) {
            enqueue(p->rch);
        }
    }
}

int treedepth(BiTree root) {
    // Calculate the height of the binary tree
    if (!root) {
        return 0;
    }
    int leftDepth = treedepth(root->lch);
    int rightDepth = treedepth(root->rch);
    return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}

void prtbtree(BiTree root, int level) {
    // Print the binary tree in a format rotated 90 degrees counterclockwise
    if (!root) {
        return;
    }
    prtbtree(root->rch, level + 1);
    for (int i = 0; i < level; i++) {
        printf("    ");
    }
    printf("%c\n", root->data);
    prtbtree(root->lch, level + 1);
}

void exchange(BiTree root) {
    // Swap the left and right subtrees of the binary tree
    if (!root) {
        return;
    }
    BiTree temp = root->lch;
    root->lch = root->rch;
    root->rch = temp;
    exchange(root->lch);
    exchange(root->rch);
}

int leafcount(BiTree root) {
    // Calculate the number of leaf nodes in the binary tree
    if (!root) {
        return 0;
    }
    if (!root->lch && !root->rch) {
        return 1;
    }
    return leafcount(root->lch) + leafcount(root->rch);
}

void paintleaf(BiTree root) {
    // Output the leaf nodes of the binary tree
    if (!root) {
        return;
    }
    if (!root->lch && !root->rch) {
        printf("%c ", root->data);
    }
    paintleaf(root->lch);
    paintleaf(root->rch);
}

BiTree CreateBinaryTree() {
    // Add your implementation for creating a binary tree
    // based on user input or any other method you prefer.
    // Return the root of the binary tree.
    return NULL;
}

HFMNode* HuffmanTreeFromBinaryTree(BiTree root) {
    if (!root) {
        return NULL;
    }

    HFMNode* hfmRoot = CreateHuffmanNode(root->data, 0);
    hfmRoot->lChild = HuffmanTreeFromBinaryTree(root->lch);
    hfmRoot->rChild = HuffmanTreeFromBinaryTree(root->rch);

    return hfmRoot;
}

HFMNode* CreateHuffmanNode(char data, int weight) {
    HFMNode* node = (HFMNode*)malloc(sizeof(HFMNode));
    node->data = data;
    node->weight = weight;
    node->lChild = NULL;
    node->rChild = NULL;
    return node;
}

int main() {
    char ch;
    int k;
    BiTree binaryTree = NULL;
    HFMNode* huffmanTree = NULL;

    do {
        printf("\n\n\n");
        printf("===================Main Menu===================\n");
        printf("1. Create Binary Tree\n");
        printf("2. Create Binary Tree (Method 1)\n");
        printf("3. Preorder Recursive Traversal\n");
        printf("4. Inorder Recursive Traversal\n");
        printf("5. Postorder Recursive Traversal\n");
        printf("6. Level Order Traversal\n");
        printf("7. Calculate Binary Tree Height\n");
        printf("8. Calculate Number of Leaf Nodes\n");
        printf("9. Swap Left and Right Subtrees\n");
        printf("10. Print Binary Tree\n");
        printf("11. Huffman Tree from Binary Tree\n");
        printf("12. Print Huffman Tree\n");  // Added option for printing Huffman Tree
        printf("0. Exit Program\n");
        printf("Enter your choice (0,1,2,3,4,5,6,7,8,9,10,11,12): ");
        scanf("%d", &k);

        switch (k) {
        case 1:
            binaryTree = CreateBinaryTree();
            huffmanTree = HuffmanTreeFromBinaryTree(binaryTree);
            break;

        case 2:
            binaryTree = creat_bt1();
            break;

        case 3:
            printf("Enter values for binary tree nodes: ");
            fflush(stdin);
            binaryTree = creat_bt2();
            break;

        case 4:
            if (binaryTree) {
                printf("Preorder traversal of the binary tree: ");
                preorder(binaryTree);
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 5:
            if (binaryTree) {
                printf("Inorder traversal of the binary tree: ");
                inorder(binaryTree);
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 6:
            if (binaryTree) {
                printf("Postorder traversal of the binary tree: ");
                postorder(binaryTree);
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 7:
            if (binaryTree) {
                printf("Level order traversal of the binary tree: ");
                levorder(binaryTree);
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 8:
            if (binaryTree) {
                printf("Height of the binary tree: %d\n", treedepth(binaryTree));
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 9:
            if (binaryTree) {
                printf("Number of leaf nodes in the binary tree: %d\n", leafcount(binaryTree));
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 10:
            if (binaryTree) {
                printf("Swap left and right subtrees:\n");
                exchange(binaryTree);
                prtbtree(binaryTree, 0);
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 11:
            if (binaryTree) {
                printf("90-degree counterclockwise rotated binary tree:\n");
                prtbtree(binaryTree, 0);
                printf("\n");
            }
            else {
                printf("Binary tree is empty!\n");
            }
            break;

        case 12:
            if (huffmanTree) {
                printf("Huffman Tree:\n");
                prtbtree((BiTree)huffmanTree, 0);
                printf("\n");
            }
            else {
                printf("Huffman Tree is empty!\n");
            }
            break;

        case 0:
            exit(0);
        }
    } while (k >= 1 && k <= 12);


    printf("\nGoodbye! Press Enter to return...\n");
    ch = getchar();
    return 0;
}
